﻿/*栈*/
#ifndef STACK_H
#define STACK_H

#include <stack>
#include <vector>
using namespace std;

/*1 两个栈实现队列
*思路：队列的特点，先进先出。
*
*/
template <typename T> class MyQueue{
public:
    void appendTail(const T&elem);
    T deleteHead();
private:
    stack<T>m_stackIn,m_stackOut;
};

void Q1_test();

/* 2 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
* 思路：设计2个栈，
* 1）入栈时，将数据与辅助栈比较，如果小于等于辅助栈，将数据压入两个栈；否则，只压入主栈。
* 2）出栈时，如果两个栈顶元素相同，同时出栈，否则，辅助栈不出栈。
* 3）获取最小值，调用min函数，只输出辅助栈顶元素，该元素不出栈。
*/

class Q2_Stack{
public:
    int top(){
        return m_stack.top();
    }

    void pop(){
        if(m_stack.top() == m_assistStack.top())
            m_assistStack.pop();
        m_stack.pop();
    }
    void push(const int&num){
        m_stack.push(num);

        if(m_assistStack.empty())
            m_assistStack.push(num);
        else if(num<=m_assistStack.top())
            m_assistStack.push(num);

    }
    int min(){
        return m_assistStack.top();
    }
private:
    stack<int> m_stack,m_assistStack;
};
void Q2_test();
/*3 栈的压入、弹出序列
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等。
 * 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
 * 但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
 * 思路：入栈序列依次入栈，同时比较栈顶元素与出栈序列，如果两者相同，出栈；如果两者不同，入栈。
 * 当栈空时，出栈序列还有数据，则不是弹出序列。否则，出栈序列式弹出序列。
 *
 */
void Q3_test();
bool Q3_IsPopOrder(vector<int> pushV,vector<int> popV);

#endif
